/* Simplethreads Instructional Thread Package
 *
 * sthread_user.c - Implements the sthread API using user-level threads.
 *
 *    You need to implement the routines in this file.
 *
 * Change Log:
 * 2002-04-15        rick
 *   - Initial version.
 * 2005-10-12        jccc
 *   - Added semaphores, deleted conditional variables
 */

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <sthread.h>
#include <sthread_user.h>
#include <sthread_ctx.h>
#include <sthread_time_slice.h>
#include <sthread_user.h>
#include "queue.h"
#include"red_black_tree.h"
#include<stdio.h>
#include<ctype.h>
#include<limits.h>

#define CLOCK_TICK 10000
#define MIN_DELAY 5

typedef struct client_t client_t;

struct client_t {
	int id;
	int num_thr;
	rb_red_blk_tree *thr_list;
};

enum sthread_state {
	RUNNING, SLEEPING, WAITING
};

struct _sthread {
	sthread_ctx_t *saved_ctx;
	sthread_start_func_t start_routine_ptr;
	long wake_time;
	int join_tid;
	void* join_ret;
	void* args;
	int tid; /* meramente informativo */
	client_t *client;
	long vruntime;
	int prio;
	int nice;
	int ticks; // numero de ticks consecutivos, volta a 0 quando perde processador
	long onThisStateSince;
	float runtime;
	float onstatefor;
	float sleeptime;
	float waittime;
	enum sthread_state state;
};


/*********************************************************************/
/* Variaveis Globais                     */
/*********************************************************************/
static sthread_t active_thr; /* thread activa */
static int tid_gen; /* gerador de tid's */
static long Clock;
static rb_red_blk_tree *exe_thr_list;
static queue_t *dead_thr_list;

/**
 * live_thr_list: threads que estao vivas( exe,sleep,join,bloqueadas num trinco),
 * ordenadas por tid
 */
static rb_red_blk_tree *live_thr_list;

/* client_list: lista de clientes com pelo menos uma thread viva ordenadas por id
 * NullFunction
 */
static rb_red_blk_tree *client_list;

/*
 *  zombie_thr_list: lista de threads zombie ordenadas por tid crescente
 */
static rb_red_blk_tree *zombie_thr_list;
/*
 *  blocked_thr_list: lista de threads bloqueados ordenadas por tid crescente
 */
static rb_red_blk_tree *blocked_thr_list;

/*
 * join_thr_list: lista de threads em estado join ordenadas por join_tid
 */
static rb_red_blk_tree *join_thr_list;

/*
 * sleep_thr_list: lista de threads a dormir ordenadas por waketime crescente
 */
static rb_red_blk_tree *sleep_thr_list;

void createBlocked();
void insertBlocked(sthread_t s);

/**
 * return true is given tree is empty
 */
int RBTreeEmpty(rb_red_blk_tree *tree) {
	return (tree->root->left == tree->nil);
}

/**
 * return lowest node on the given tree
 */

rb_red_blk_node* RBTreeLowest(rb_red_blk_tree *tree) {
	rb_red_blk_node* lowest = tree->root->left;
	rb_red_blk_node* nil = tree->nil;
	if (lowest == nil)
		return tree->nil;

	while (lowest->left != nil) {
		lowest = lowest->left;
	}
	return lowest;
}

/***************************************/
/* IntComp */
/***************************************/
int IntComp(const void* a, const void* b) {
	if (*(int*) a > *(int*) b)
		return (1);
	if (*(int*) a < *(int*) b)
		return (-1);
	return (0);
}

/***************************************/
/* LongComp */
/***************************************/
int LongComp(const void* a, const void* b) {
	if (*(long*) a > *(long*) b)
		return (1);
	if (*(long*) a < *(long*) b)
		return (-1);
	return (0);
}

/***************************************/
/* LongComp: dummy function */
/***************************************/
void NullFunctionn(const void*s) {
}

/**
 * exe_thr_list: lista de threads executaveis ordenadas por vruntime crescente
 */

void createExe() {
	exe_thr_list = RBTreeCreate(LongComp, NullFunction, NullFunction,
			NullFunctionn, NullFunction);
}

void insertExe(sthread_t t) {
	t->onThisStateSince = Clock;
	t->state = WAITING;
	RBTreeInsert(exe_thr_list, &(t->vruntime), t);
}

sthread_t getExe() {
	sthread_t thr;
	rb_red_blk_node *lowest = RBTreeLowest(exe_thr_list);
	assert((lowest != exe_thr_list->nil));
	thr = (sthread_t) lowest->info;
	RBDelete(exe_thr_list, lowest);
	thr->waittime += Clock - thr->onThisStateSince;
	thr->onThisStateSince = Clock;
	thr->state = RUNNING;
	thr->ticks = 0;
	return thr;
}

/***************************************/
/* dead_thr_list:  lista de threads "mortas"*/
/***************************************/

void createDead() {
	dead_thr_list = create_queue();
}

void createSleep() {
	sleep_thr_list = RBTreeCreate(LongComp, NullFunction, NullFunction,
			NullFunctionn, NullFunction);
}

void insertSleep(sthread_t t) {
	t->onThisStateSince = Clock;
	t->state = SLEEPING;
	RBTreeInsert(sleep_thr_list, &(t->wake_time), t);
}

sthread_t findSleep(long time) {
	rb_red_blk_node *node = RBExactQuery(sleep_thr_list, &(time));
	sthread_t thr = NULL;
	if (node != NULL) {
		thr = (sthread_t) node->info;
		RBDelete(sleep_thr_list, node);
		thr->sleeptime += Clock - thr->onThisStateSince;
		thr->wake_time = 0;
	}
	return thr;
}

void createJoin() {
	join_thr_list = RBTreeCreate(IntComp, NullFunction, NullFunction,
			NullFunctionn, NullFunction);
}

void insertJoin(sthread_t t) {
	t->onThisStateSince = Clock;
	t->state = SLEEPING;
	RBTreeInsert(join_thr_list, &(t->join_tid), t);
}

sthread_t findJoin(int tid) {
	rb_red_blk_node *node = RBExactQuery(join_thr_list, &(active_thr->tid));
	sthread_t thr = NULL;
	if (node != NULL) {
		thr = (sthread_t) node->info;
		RBDelete(join_thr_list, node);
		thr->sleeptime += Clock - thr->onThisStateSince;

	}
	return thr;

}

void createZombie() {
	zombie_thr_list = RBTreeCreate(IntComp, NullFunction, NullFunction,
			NullFunctionn, NullFunction);
}

void insertZombie(sthread_t t) {
	RBTreeInsert(zombie_thr_list, &(t->join_tid), t);
}

void createBlocked() {
	blocked_thr_list = RBTreeCreate(IntComp, NullFunction, NullFunction,
			NullFunctionn, NullFunction);
}
void insertBlocked(sthread_t t) {
	RBTreeInsert(blocked_thr_list, &(t->tid), t);
}

void removeBlocked(sthread_t t) {
	rb_red_blk_node *node = RBExactQuery(blocked_thr_list, &(t->tid));
	RBDelete(blocked_thr_list, node);
}

void createLive() {
	live_thr_list = RBTreeCreate(IntComp, NullFunction, NullFunction,
			NullFunctionn, NullFunction);
}

void insertLive(sthread_t t) {
	RBTreeInsert(live_thr_list, &(t->tid), t);
}

sthread_t findLive(int id) {
	rb_red_blk_node *node = RBExactQuery(live_thr_list, &(id));
	RBDelete(live_thr_list, node);
	sthread_t thr = NULL;
	return thr;
}

void createClientList() {
	client_list = RBTreeCreate(IntComp, NullFunction, NullFunction,
			NullFunctionn, NullFunction);
}

client_t* getClient(int clientID) {
	rb_red_blk_node* node = RBExactQuery(client_list, &clientID);
	if (node != NULL) {
		return (client_t*) node->info;
	} else {
		return NULL;
	}
}

client_t* newClient(int clientID) {
	client_t* client = (client_t*) malloc(sizeof(client_t));
	client->id = clientID;
	client->num_thr = 0;
	client->thr_list = RBTreeCreate(IntComp, NullFunction, NullFunction,
			NullFunctionn, NullFunction);
	RBTreeInsert(client_list, &(client->id), client);
	return client;
}

void clientAddThread(client_t *client, sthread_t thread) {
	assert( client != NULL && thread != NULL);
	client->num_thr++;
	RBTreeInsert(client->thr_list, &(thread->tid), thread);
}

void clientRemoveThread(client_t *client, sthread_t thread) {
	assert( client != NULL && thread != NULL);
	rb_red_blk_node* threadNode = RBExactQuery(client->thr_list,
			&(thread->tid));
	assert( (threadNode != NULL));
	RBDelete(client->thr_list, threadNode);
	client->num_thr--;
}

void removeClient(int clientID) {
	rb_red_blk_node* clientNode = RBExactQuery(client_list, &clientID);
	assert( (clientNode != NULL));
	client_t* c = (client_t*) clientNode->info;
	assert( c->num_thr == 0);
	RBDelete(client_list, clientNode);
	free(c);
}

/*********************************************************************/
/* Declaracoes                     */
/*********************************************************************/
void DumpClient(client_t* c);
void sthread_user_free(sthread_t thread);
int RBTreeEmpty(rb_red_blk_tree *tree);
rb_red_blk_node* RBTreeLowest(rb_red_blk_tree *tree);

void CleanExit();
client_t* getClient(int);

/*********************************************************************/
/* Funcoes para usar na RBT                     */
/*********************************************************************/

/**
 * Se nao existirem mais threads em execução
 */
void CleanExit() {
	if (RBTreeEmpty(exe_thr_list)) {
		RBTreeDestroy(exe_thr_list);
		delete_queue(dead_thr_list);
		sthread_user_free(active_thr);
		printf("Exec queue is empty!\n");
		exit(0);
	}
}

void PrintThreadKey(const void* t) {
	printf("thr->vruntime=%d", *((int*) t));
}
void PrintThreadInfo(void* t) {
	sthread_t temp = (sthread_t) t;
	printf("thr_tid=%d", temp->tid);
}
void PrintClientKey(const void* t) {
	printf("client->id=%d", *((int*) t));
}
void PrintClientInfo(void* t) {
	client_t* c = (client_t*) t;
	printf("client->num_thr=%d", c->num_thr);
}

void DumpThread(sthread_t t) {
	printf("tid:%d|", t->tid);
	printf("vruntime:%ld|", t->vruntime);
	DumpClient(t->client);
	printf("wake_time:%ld|", t->wake_time);
	printf("join_tid:%d| ", t->join_tid);
	printf("prio:%d|", t->prio);
	printf("nice:%d|", t->nice);
	printf("ticks:%d\n", t->ticks);
}

void DumpClient(client_t* c) {
	printf("client->id:%d|", c->id);
	printf("client->num_thr:%d|", c->num_thr);
}

void sthread_user_free(sthread_t thread) {
	sthread_free_ctx(thread->saved_ctx);
	free(thread);
}

void client_free(void* a) {
	free((client_t*) a);
}

/*********************************************************************/
/* Part 1: Creating and Scheduling Threads                           */
/*********************************************************************/
void sthread_user_dispatcher(void);

void sthread_aux_start(void) {
	splx(LOW);
	active_thr->start_routine_ptr(active_thr->args);
	sthread_user_exit((void*) 0);
}

void sthread_user_init(void) {
	createExe();
	createDead();
	createSleep();
	createJoin();

	createBlocked();
	createZombie();
	createLive();
	createClientList();
	client_t* main_client = newClient(0);
	tid_gen = 0;
	Clock = 1;
	sthread_t main_thread = malloc(sizeof(struct _sthread));
	main_thread->saved_ctx = sthread_new_blank_ctx();
	main_thread->start_routine_ptr = NULL;
	main_thread->wake_time = 0;
	main_thread->join_tid = 0;
	main_thread->join_ret = NULL;
	main_thread->args = NULL;
	main_thread->tid = tid_gen++;
	main_thread->client = main_client;
	main_thread->vruntime = 0;
	main_thread->prio = 1;
	main_thread->nice = 0;
	main_thread->ticks = 0;
	main_thread->runtime = 0;
	main_thread->onstatefor = 0;
	main_thread->sleeptime = 0;
	main_thread->waittime = 0;
	main_thread->onThisStateSince = 1;
	main_thread->state = RUNNING;
	active_thr = main_thread;
	clientAddThread(main_client, main_thread);
	insertLive(main_thread);
	sthread_time_slices_init(sthread_user_dispatcher, CLOCK_TICK);
}

sthread_t sthread_user_create(sthread_start_func_t start_routine, void *arg,
		int clientID, int priority, int nice) {

	splx(HIGH);
	struct _sthread *new_thread = (struct _sthread*) malloc(
			sizeof(struct _sthread));
	sthread_ctx_start_func_t func = sthread_aux_start;
	new_thread->saved_ctx = sthread_new_ctx(func);
	new_thread->start_routine_ptr = start_routine;
	new_thread->wake_time = 0;
	new_thread->join_tid = 0;
	new_thread->join_ret = NULL;
	new_thread->args = arg;
	new_thread->vruntime = active_thr->vruntime;
	new_thread->prio = priority;
	new_thread->nice = nice;
	new_thread->ticks = 0;
	new_thread->runtime = 0;
	new_thread->onstatefor = 0;
	new_thread->sleeptime = 0;
	new_thread->waittime = 0;

	client_t* client = getClient(clientID);
	if (client == NULL) {
		client = newClient(clientID);
	}
	new_thread->client = client;
	new_thread->tid = ++tid_gen;
	new_thread->state = WAITING;
	new_thread->onThisStateSince = Clock;
	clientAddThread(client, new_thread);
	insertExe(new_thread);
	insertLive(new_thread);
	splx(LOW);
	return new_thread;
}

void sthread_user_exit(void *ret) {
	splx(HIGH);
	int is_zombie = 1;
	sthread_t thr;
	//desbloqueia todas as threads que fizeram join a si (active_thr)
	while ((thr = findJoin(active_thr->tid)) != NULL) {
		removeBlocked(thr);
		thr->state = WAITING;
		thr->onThisStateSince = Clock;
		insertExe(thr);
		is_zombie = 0;
	}

	//a thread deixa de estar viva
	findLive(active_thr->tid);

	if (is_zombie) {
		insertZombie(active_thr);
	} else {
		queue_insert(dead_thr_list, active_thr);
	}

	// decrementa num_thr do client, e se for a unica thread, remove o client
	clientRemoveThread(active_thr->client, active_thr);
	if (active_thr->client->num_thr == 0) {
		removeClient(active_thr->client->id);
	}
	CleanExit();
	sthread_t old_thr = active_thr;
	active_thr->onThisStateSince = Clock;
	active_thr = getExe();
	sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);
	splx(LOW);
}

void sthread_user_dispatcher(void) {
	splx(HIGH);
	Clock++;
	rb_red_blk_node* lowest = NULL;
	rb_red_blk_node* node = NULL;
	rb_red_blk_node* nil = NULL;
	sthread_t tmp = NULL;
	long min_vruntime = LONG_MAX;
	// tratamento de overflow de vruntime
	long vruntime = (active_thr->prio + active_thr->nice)
			* (active_thr->client->num_thr);
	long dif = LONG_MAX - active_thr->vruntime;
	if (vruntime >= dif) {

		nil = live_thr_list->nil;
		// encontram o menor vruntime da threads vivas
		lowest = node = RBTreeLowest(live_thr_list);
		tmp = (sthread_t) node->info;
		assert((node != live_thr_list->nil));
		min_vruntime = tmp->vruntime;
		while ((node = TreeSuccessor(live_thr_list, node)) != nil) {
			tmp = (sthread_t) node->info;
			if (tmp->vruntime < min_vruntime) {
				min_vruntime = tmp->vruntime;
			}
		}
		// subtrair o menor vruntime a cada thread viva
		node = lowest;
		tmp = (sthread_t) node->info;
		tmp->vruntime -= min_vruntime;
		node = TreeSuccessor(live_thr_list, node);
		while (node != nil) {
			tmp = (sthread_t) node->info;
			tmp->vruntime -= min_vruntime;
			node = TreeSuccessor(live_thr_list, node);
		}
	}

	active_thr->vruntime += vruntime;
	active_thr->ticks++;

	sthread_t thr;
	//move todas as threads com wake_time == Clock para a lista das threads executaveis
	while ((thr = findSleep(Clock)) != NULL) {
		removeBlocked(thr);
		insertExe(thr);
	}
	//preemption	
	if (active_thr->ticks >= MIN_DELAY) {
		active_thr->runtime += active_thr->ticks;
		insertExe(active_thr);
		sthread_t old_thr = active_thr;
		active_thr = getExe();
		sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);
	}
	splx(LOW);
}

void sthread_user_yield(void) {
	splx(HIGH);
	active_thr->runtime += active_thr->ticks;
	insertExe(active_thr);
	sthread_t old_thr = active_thr;
	active_thr = getExe();
	sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);
	splx(LOW);
}

/*********************************************************************/
/* Part 2: Join and Sleep Primitives                                 */
/*********************************************************************/

int sthread_user_join(sthread_t thread, void **value_ptr) {
	/* suspends execution of the calling thread until the target thread
	 terminates, unless the target thread has already terminated.
	 On return from a successful pthread_join() call with a non-NULL
	 value_ptr argument, the value passed to pthread_exit() by the
	 terminating thread is made available in the location referenced
	 by value_ptr. When a pthread_join() returns successfully, the
	 target thread has been terminated. The results of multiple
	 simultaneous calls to pthread_join() specifying the same target
	 thread are undefined. If the thread calling pthread_join() is
	 canceled, then the target thread will not be detached.

	 If successful, the pthread_join() function returns zero.
	 Otherwise, an error number is returned to indicate the error. */

	splx(HIGH);

	// checks if the thread to wait is zombie
	int found = 0;
	rb_red_blk_node* node;

	if (NULL != (node = RBExactQuery(zombie_thr_list, &(thread->tid)))) {
		sthread_t zthread = (sthread_t) node->info;
		RBDelete(zombie_thr_list, node);
		queue_insert(dead_thr_list, zthread);
		found = 1;
	}

	if (found) {
		splx(LOW);
		return 0;
	}

	// search active queue
	if (active_thr->tid == thread->tid) {
		found = 1;
	}
	//a thread deixa de estar viva
	node = RBExactQuery(live_thr_list, &(thread->tid));
	if (node != NULL) {
		found = 1;
	}

	// if found blocks until thread ends
	if (!found) {
		splx(LOW);
		return -1;
	} else {
		active_thr->runtime += active_thr->ticks;
		active_thr->join_tid = thread->tid;
		insertJoin(active_thr);
		insertBlocked(active_thr);
		sthread_t old_thr = active_thr;
		active_thr = getExe();
		sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);
		*value_ptr = thread->join_ret;
	}
	splx(LOW);
	return 0;
}

/* minimum sleep time of 1 clocktick.
 1 clock tick, value 10 000 = 10 ms */

int sthread_user_sleep(int time) {
	splx(HIGH);
	long num_ticks = time / CLOCK_TICK;
	if (num_ticks <= 0) {
		splx(LOW);
		return 0;
	}
	active_thr->wake_time = Clock + num_ticks;
	active_thr->runtime += active_thr->ticks;
	insertSleep(active_thr);
	insertBlocked(active_thr);
	CleanExit();
	sthread_t old_thr = active_thr;
	active_thr = getExe();
	sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);

	splx(LOW);
	return 0;
}

int sthread_nice(int nice) {
	int result;
	if (!(0 <= nice && nice <= 10))
		return -1;
	splx(HIGH);
	active_thr->nice = nice;
	result = active_thr->nice + active_thr->prio;
	splx(LOW);
	return result;
}

/* --------------------------------------------------------------------------*
 * Synchronization Primitives                                                *
 * ------------------------------------------------------------------------- */

/*
 * Mutex implementation
 */

struct _sthread_mutex {
	lock_t l;
	struct _sthread *thr;
	queue_t* queue;
};

sthread_mutex_t sthread_user_mutex_init() {
	sthread_mutex_t lock;

	if (!(lock = malloc(sizeof(struct _sthread_mutex)))) {
		printf("Error in creating mutex\n");
		return 0;
	}

	/* mutex initialization */
	lock->l = 0;
	lock->thr = NULL;
	lock->queue = create_queue();

	return lock;
}

void sthread_user_mutex_free(sthread_mutex_t lock) {
	delete_queue(lock->queue);
	free(lock);
}

void sthread_user_mutex_lock(sthread_mutex_t lock) {
	while (atomic_test_and_set(&(lock->l))) {
	}
	if (lock->thr == NULL) {
		lock->thr = active_thr;
		atomic_clear(&(lock->l));
	} else {
		queue_insert(lock->queue, active_thr);
		atomic_clear(&(lock->l));
		splx(HIGH);
		active_thr->runtime += Clock - active_thr->onThisStateSince;
		active_thr->onThisStateSince = Clock;
		active_thr->state = SLEEPING;
		insertBlocked(active_thr);
		sthread_t old_thr = active_thr;
		active_thr = getExe();
		sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);
		splx(LOW);
	}
}

void sthread_user_mutex_unlock(sthread_mutex_t lock) {
	if (lock->thr != active_thr) {
		printf("unlock without lock!\n");
		return;
	}
	sthread_t unlocked_thr = NULL;
	while (atomic_test_and_set(&(lock->l))) {
	}
	if (queue_is_empty(lock->queue)) {
		lock->thr = NULL;
		atomic_clear(&(lock->l));
		return;
	} else {
		unlocked_thr = lock->thr = queue_remove(lock->queue);
	}
	atomic_clear(&(lock->l));

	splx(HIGH);
	unlocked_thr->sleeptime += Clock - unlocked_thr->onThisStateSince;
	unlocked_thr->onThisStateSince = Clock;
	removeBlocked(unlocked_thr);

	if (active_thr->ticks >= MIN_DELAY
			&& unlocked_thr->vruntime < active_thr->vruntime) {
		active_thr->runtime += Clock - active_thr->onThisStateSince;
		insertExe(active_thr);
		sthread_t old_thr = active_thr;
		active_thr = unlocked_thr;
		unlocked_thr->state = RUNNING;
		//active_thr->ticks=0;
		sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);
	} else {
		insertExe(unlocked_thr);
	}
	splx(LOW);

}

/*------------
 Semaphore Implementation
 */

struct _sthread_sem {
	unsigned int value;
	queue_t* queue;
	lock_t l; // lock
};

sthread_sem_t sthread_user_sem_init(unsigned int initial_count) {
	sthread_sem_t sem;
	if (!(sem = malloc(sizeof(struct _sthread_sem)))) {
		printf("Error in creating semaphore\n");
		return 0;
	}
	/* initialization */
	sem->l = 0;
	sem->value = initial_count;
	sem->queue = create_queue();
	return sem;
}

void sthread_user_sem_wait(sthread_sem_t s) {
	while (atomic_test_and_set(&(s->l))) {
	}

	if (s->value == 0) {
		queue_insert(s->queue, active_thr);
		atomic_clear(&(s->l));
		splx(HIGH);
		active_thr->runtime += active_thr->ticks;
		active_thr->state = SLEEPING;
		active_thr->onThisStateSince = Clock;
		insertBlocked(active_thr);
		sthread_t old_thr = active_thr;
		active_thr = getExe();
		//active_thr->ticks=0;
		sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);
		splx(LOW);
	} else {
		s->value--;
		atomic_clear(&(s->l));
	}
}

void sthread_user_sem_post(sthread_sem_t s) {
	while (atomic_test_and_set(&(s->l))) {
	}
	sthread_t unlocked_thr = NULL;
	sthread_t old_thr = NULL;
	s->value++;
	if (s->value == 1 && !queue_is_empty(s->queue)) { //existem threads bloqueadas
		unlocked_thr = queue_remove(s->queue);
		s->value--;
		atomic_clear(&(s->l));
		splx(HIGH);
		unlocked_thr->sleeptime += Clock - unlocked_thr->onThisStateSince;
		unlocked_thr->onThisStateSince = Clock;
		removeBlocked(unlocked_thr);
		if (active_thr->ticks >= MIN_DELAY
				&& unlocked_thr->vruntime < active_thr->vruntime) {
			active_thr->runtime += Clock - active_thr->onThisStateSince;
			insertExe(active_thr);
			old_thr = active_thr;
			active_thr = unlocked_thr;
			active_thr->state = RUNNING;
			sthread_switch(old_thr->saved_ctx, active_thr->saved_ctx);
		} else {
			insertExe(unlocked_thr);
		}
		splx(LOW);

	} else {
		atomic_clear(&(s->l));
	}
}

/*
 * Readers/Writer implementation
 */

struct _sthread_rwlock {
	int nleitores;
	int /*boolean_t*/em_escrita;
	int leitores_espera;
	int escritores_espera;
	sthread_mutex_t m;
	sthread_sem_t leitores;
	sthread_sem_t escritores;
};

void sthread_user_rwlock_destroy(sthread_rwlock_t rwlock) {

	sthread_user_mutex_free(rwlock->m);
	sthread_user_sem_destroy(rwlock->leitores);
	sthread_user_sem_destroy(rwlock->escritores);
	free(rwlock);

}

sthread_rwlock_t sthread_user_rwlock_init() {

	sthread_rwlock_t rwlock;

	if (!(rwlock = malloc(sizeof(struct _sthread_rwlock)))) {
		printf("Error in creating rwlock\n");
		return 0;
	}

	rwlock->leitores = sthread_user_sem_init(0);
	rwlock->escritores = sthread_user_sem_init(0);
	rwlock->m = sthread_user_mutex_init();
	rwlock->nleitores = 0;
	rwlock->em_escrita = 0; /*FALSE;*/
	rwlock->leitores_espera = 0;
	rwlock->escritores_espera = 0;

	return rwlock;

}

void sthread_user_rwlock_rdlock(sthread_rwlock_t rwlock) {

	sthread_user_mutex_lock(rwlock->m);
	if (rwlock->em_escrita || rwlock->escritores_espera > 0) {
		rwlock->leitores_espera++;
		sthread_user_mutex_unlock(rwlock->m);
		sthread_user_sem_wait(rwlock->leitores);
		sthread_user_mutex_lock(rwlock->m);
	} else {
		rwlock->nleitores++;
	}
	sthread_user_mutex_unlock(rwlock->m);

}

void sthread_user_rwlock_wrlock(sthread_rwlock_t rwlock) {

	sthread_user_mutex_lock(rwlock->m);
	if (rwlock->em_escrita || rwlock->nleitores > 0) {
		rwlock->escritores_espera++;
		sthread_user_mutex_unlock(rwlock->m);
		sthread_user_sem_wait(rwlock->escritores);
		sthread_user_mutex_lock(rwlock->m);
	} else {
		rwlock->em_escrita = 1; /*TRUE;*/
	}
	sthread_user_mutex_unlock(rwlock->m);

}

void sthread_user_rwlock_unlock(sthread_rwlock_t rwlock) {
	int i;
	sthread_user_mutex_lock(rwlock->m);

	if (/*TRUE*/1 == rwlock->em_escrita) { /* writer unlock*/

		rwlock->em_escrita = 0; /*FALSE; */
		if (rwlock->leitores_espera > 0) {
			for (i = 0; i < rwlock->leitores_espera; i++) {
				sthread_user_sem_post(rwlock->leitores);
				rwlock->nleitores++;
			}
			rwlock->leitores_espera -= i;
		} else {
			if (rwlock->escritores_espera > 0) {
				sthread_user_sem_post(rwlock->escritores);
				rwlock->em_escrita = 1; /*TRUE;*/
				rwlock->escritores_espera--;
			}
		}
	} else { /* reader unlock*/

		rwlock->nleitores--;
		if (rwlock->nleitores == 0 && rwlock->escritores_espera > 0) {
			sthread_user_sem_post(rwlock->escritores);
			rwlock->em_escrita = 1; /*TRUE;*/
			rwlock->escritores_espera--;
		}
	}
	sthread_user_mutex_unlock(rwlock->m);
}

void sthread_user_sem_destroy(sthread_sem_t s) {
	delete_queue(s->queue);
	free(s);
}

/*
 * Monitor implementation
 */

struct _sthread_mon {
	sthread_mutex_t mutex;
	queue_t* queue;
};

sthread_mon_t sthread_user_monitor_init() {
	printf("WARNING: pthreads do not include monitors!\n");
	return NULL;
}

void sthread_user_monitor_free(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");
}

void sthread_user_monitor_enter(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");

}

void sthread_user_monitor_exit(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");

}

void sthread_user_monitor_wait(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");

}

void sthread_user_monitor_signal(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");

}

void sthread_user_monitor_signalall(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");

}

/* The following functions are dummies to 
 * highlight the fact that pthreads do not
 * include monitors.
 */

sthread_mon_t sthread_dummy_monitor_init() {
	printf("WARNING: pthreads do not include monitors!\n");
	return NULL;
}

void sthread_dummy_monitor_free(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");
}

void sthread_dummy_monitor_enter(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");
}

void sthread_dummy_monitor_exit(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");
}

void sthread_dummy_monitor_wait(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");
}

void sthread_dummy_monitor_signal(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");
}

void sthread_dummy_monitor_signalall(sthread_mon_t mon) {
	printf("WARNING: pthreads do not include monitors!\n");
}

/**
 *  DUMPS
 *
 */

void sthread_dump_aux(sthread_t t) {
	printf("id: %d ", t->client->id);
	printf("request: %d ", t->tid);
	printf("priority: %d ", (t->prio + t->nice));
	printf("vruntime: %ld\n", t->vruntime);
	printf("runtime: %.0f ", t->runtime);
	printf("on state for %ld ", Clock - t->onThisStateSince);
	printf("sleeptime %.0f ", t->sleeptime);
	printf("waitime %.0f\n", t->waittime);
}

void sthread_dump_active() {
	printf("Active thread\n");
	sthread_dump_aux(active_thr);
	printf("\n\n");
}
/*
 *
 nil = live_thr_list->nil;
 // encontram o menor vruntime da threads vivas
 lowest = node = RBTreeLowest(live_thr_list);
 tmp = (sthread_t) node->info;
 assert((node != NULL));
 min_vruntime = tmp->vruntime;
 while ((node = TreeSuccessor(live_thr_list, node)) != nil) {
 tmp = (sthread_t) node->info;
 if (tmp->vruntime < min_vruntime) {
 min_vruntime = tmp->vruntime;
 }
 }
 */

void sthread_dump_scheduler() {
	printf(">>>> Scheduler <<<<\n");
	rb_red_blk_node* client_node;
	rb_red_blk_node* thr_node;
	rb_red_blk_node* client_nil;
	rb_red_blk_node* thr_nil;
	rb_red_blk_tree * thr_list;
	client_t * client;
	sthread_t tmp;
	client_nil = client_list->nil;
	client_node = RBTreeLowest(client_list);
	while (client_node != client_nil) {
		client = (client_t *) client_node->info;
		thr_list = client->thr_list;
		thr_nil = thr_list->nil;
		thr_node = RBTreeLowest(thr_list);
		while (thr_node != thr_nil) {
			tmp = (sthread_t) thr_node->info;
			sthread_dump_aux(tmp);
			thr_node = TreeSuccessor(thr_list, thr_node);
		}
		client_node = TreeSuccessor(client_list, client_node);
	}

	printf("\n\n");
}
void sthread_dump_blocked() {
	printf(">>>>BlockedList<<<<\n");
	rb_red_blk_node * node;
	rb_red_blk_node* thr_nil = blocked_thr_list->nil;
	sthread_t tmp;
	for (node = RBTreeLowest(blocked_thr_list); node != thr_nil; node =
			TreeSuccessor(blocked_thr_list, node)) {
		tmp = (sthread_t) node->info;
		sthread_dump_aux(tmp);
	}
	printf("\n\n");
}

void sthread_dump_sleep() {
	printf(">>>>SleepList<<<<\n");
	rb_red_blk_node * node = RBTreeLowest(sleep_thr_list);
	if (node == sleep_thr_list->nil)
		return;
	rb_red_blk_node * nil = sleep_thr_list->nil;
	sthread_t tmp;
	while (node != nil) {
		tmp = (sthread_t) node->info;
		sthread_dump_aux(tmp);
		printf("Waketime: %ld", tmp->wake_time);
		node = TreeSuccessor(sleep_thr_list, node);
	}
	printf("\n\n");
}

void sthread_dump() {
	splx(HIGH);
	printf("=== dump start ===\n");
	sthread_dump_active();
	sthread_dump_scheduler();
	sthread_dump_blocked();
	sthread_dump_sleep();
	printf("== == Dump End == ==\n");
	splx(LOW);
}
